DROPS

Document

DOI: 10.4230/LIPIcs.ICALP.2016.79

Correlation Decay and Tractability of CSPs

Authors: Jonah Brown-Cohen and Prasad Raghavendra

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract

The algebraic dichotomy conjecture of Bulatov, Krokhin and Jeavons yields an elegant characterization of the complexity of constraint satisfaction problems. Roughly speaking, the characterization asserts that a CSP L is tractable if and only if there exist certain non-trivial operations known as polymorphisms to combine solutions to L to create new ones. In this work, we study the dynamical system associated with repeated applications of a polymorphism to a distribution over assignments. Specifically, we exhibit a correlation decay phenomenon that makes two variables or groups of variables that are not perfectly correlated become independent after repeated applications of a polymorphism. We show that this correlation decay phenomenon can be utilized in designing algorithms for CSPs by exhibiting two applications: 1. A simple randomized algorithm to solve linear equations over a prime field, whose analysis crucially relies on correlation decay. 2. A sufficient condition for the simple linear programming relaxation for a 2-CSP to be sound (have no integrality gap) on a given instance.

Cite as

Jonah Brown-Cohen and Prasad Raghavendra. Correlation Decay and Tractability of CSPs. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 79:1-79:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{browncohen_et_al:LIPIcs.ICALP.2016.79,
  author =	{Brown-Cohen, Jonah and Raghavendra, Prasad},
  title =	{{Correlation Decay and Tractability of CSPs}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{79:1--79:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.79},
  URN =		{urn:nbn:de:0030-drops-62064},
  doi =		{10.4230/LIPIcs.ICALP.2016.79},
  annote =	{Keywords: Constraint Satisfaction, Polymorphisms, Linear Equations, Correlation Decay}
}

Search Results

Documents authored by Brown-Cohen, Jonah

Correlation Decay and Tractability of CSPs

Abstract

Cite as

Thanks for your feedback!

Could not send message